import java.util.Hashtable;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Map.Entry;

import org.junit.Test;

public class MyTest {
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;
    
        public Node() {}
        
        public Node(int _val) {
            val = _val;
        }
    
        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }
    public Node connect(Node root) {
        Node head=root;
        while(head!=null){
            head.left.next=head.right;
            Node curr=head;
            while(curr.next!=null){
                curr.right.next=curr.next.left;
                curr=curr.next;
                curr.left.next=curr.right;
            }
            head=head.left;
        }
        return root;
    }

    public int subarraySum(int[] nums, int k) {
        Hashtable<Integer,Integer> hashtable=new Hashtable<Integer,Integer>();
        hashtable.put(0, 1);
        int pre=0;
        int ans=0;
        for(int num:nums){
            pre+=num;
            if(hashtable.containsKey(pre-k)){
                ans+=hashtable.get(pre-k);
            }
            if(hashtable.containsKey(pre)){
                int newCount=hashtable.get(pre);
                hashtable.replace(pre, newCount+1);
            }else{
                hashtable.put(pre, 1);
            }
        }
        return ans;
    }

    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for(int num:nums){
            sum+=num;
        }
        int diff=sum-target;
        if(diff<0||diff%2!=0){
            return 0;
        }
        int neg=diff/2;
        int[][] dp=new int[nums.length+1][neg+1];
        for(int i=0;i<=nums.length;i++){
            dp[i][0]=1;
        }
        for(int i=1;i<dp.length;i++){
            for(int j=1;j<dp[0].length;j++){
                if(j<nums[i-1]){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[nums.length][neg];
    }

    public int maxProfit(int[] prices) {
        if(prices.length==0){
            return 0;
        }
        int[][] dp=new int[prices.length][3];
        dp[0][0]=-prices[0];
        for(int i=1;i<prices.length;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
            dp[i][1]=dp[i-1][0]+prices[i];
            dp[i][2]=Math.max(dp[i-1][1], dp[i-1][2]);
        }
        return Math.max(dp[dp.length-1][1], dp[dp.length-1][2]);
    }

    public int[] productExceptSelf(int[] nums) {
        int[] ans=new int[nums.length];
        ans[0]=1;
        for(int i=1;i<ans.length;i++){
            ans[i]=ans[i-1]*nums[i-1];
        }
        int suffix=1;
        for(int i=ans.length-1;i>=0;i--){
            ans[i]*=suffix;
            suffix*=nums[i];
        }
        return ans;
    }

    public int[] topKFrequent(int[] nums, int k) {
        Hashtable<Integer,Integer> hashtable=new Hashtable<Integer,Integer>();
        for(int num:nums){
            int fre=hashtable.getOrDefault(num, 0);
            hashtable.put(num, fre+1);
        }
        Queue<Entry<Integer,Integer>> queue=new PriorityQueue<Entry<Integer,Integer>>(
            (first,second)->(second.getValue().compareTo(first.getValue()))
        );
        queue.addAll(hashtable.entrySet());
        int[] ans=new int[k];
        for(int i=0;i<k;i++){
            ans[i]=queue.poll().getKey();
        }
        return ans;
    }
    @Test
    public void test(){
        int[] nums={};
        int k=1;
        for(int num:topKFrequent(nums, k)){
            System.out.print(num+" ");
        }
    }

}
